package com.heima.leetcode.datastructure.heap;

/**
 * <strong>用自己实现的堆查找数据流的中位数 295</strong>
 * <ul>
 *     <li>如果直接遍历排序效率低</li>
 *     <li>可以把数据流分为两个相当大小的部分，前半和后半</li>
 *     <li>前半用大顶堆来存储，只关心前半部分的最大值</li>
 *     <li>后半用小顶堆来存储，只关心后半部分的最小值</li>
 *     <li>怎么保证大顶堆内元素的个数等于小顶堆内元素的个数呢
 *         <ol>
 *             <li>可以规定当两个堆中的元素个数相等时，往大顶堆中加入一个元素</li>
 *             <li>可以规定当两个堆中的元素个数不等时，往小顶堆中加入一个元素</li>
 *         </ol>
 *     </li>
 *     <li>如何保证大顶堆里面存的就是前半部分，小顶堆里面存的就是后半部分呢
 *         <ol>
 *             <li>当将要往大顶堆中放入元素时，不要直接放入，而是先放入小顶堆中，再让小顶堆重构后吐出一个堆顶元素加到小顶堆中</li>
 *             <li>当将要往小顶堆中放入元素时，不要直接放入，而是先放入大顶堆中，再让大顶堆重构后吐出一个堆顶元素加到大顶堆中</li>
 *         </ol>
 *     </li>
 *     <li>因为数据流是会变化的，会增大，所以当堆为满的时候应该实现自动扩容</li>
 * </ul>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/6 19:39
 */
public class MedianFinder1 {
    private final Heap leftHeap; // 左堆，用于存储左半部分，扩容后只是堆中的数组变量指向的数组对象变了，但是指向这个堆对象的指针不会变

    private final Heap rightHeap; // 右堆，用于存储右半部分，扩容后只是堆中的数组变量指向的数组对象变了，但是指向这个堆对象的指针不会变

    // 构造器公共代码
    {
        leftHeap = new Heap(10,true); // 用于存放左半部分的大顶堆
        rightHeap = new Heap(10,false); // 用于存放右半部分的小顶堆
    }

    /**
     * 无参构造初始化
     */
    public MedianFinder1(){
    }

    /**
     * 初始情况数据流是一个已知的数组
     * @param arr 数组
     */
    public MedianFinder1(int[] arr) {
        for (int i : arr) {
            addNum(i); // 遍历数组相当的加到两个堆中
        }
    }

    /**
     * 加入一个数据流中的元素到两个堆中
     * @param num 元素
     */
    public void addNum(int num){
        if (leftHeap.size() == rightHeap.size()){ // 相等则让左边加
            // 但是不能直接加，要先加到右边，再让右边poll出堆顶元素，以达到实现平衡
            rightHeap.offer(num);
            leftHeap.offer(rightHeap.poll());
        }else { // 不等则让右边加
            // 但是不能直接加，要先加到左边，再让左边poll出堆顶元素，以达到实现平衡
            leftHeap.offer(num);
            rightHeap.offer(leftHeap.poll());
        }
    }

    /**
     * 找出中位数
     * @return 中位数
     */
    public double findMedian(){
        if (leftHeap.isEmpty() && rightHeap.isEmpty()){
            throw new IllegalArgumentException("数据流为空");
        }
        if (leftHeap.size() > rightHeap.size()){
            return leftHeap.peek();
        } else if (leftHeap.size() < rightHeap.size()) {
            return rightHeap.peek();
        }
        return (leftHeap.peek() + rightHeap.peek()) / 2.0;
    }

    @Override
    public String toString() {
        return "左半部分：" +
                leftHeap.toString() +
                " "+
                rightHeap.toString() +
                "：右半部分" ;
    }
}
